package leetcode;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

/**
 * Created by Ghost on 2014/10/7.
 */

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
}

public class Copy_List_with_Random_Pointer {
    public static RandomListNode copyRandomList(RandomListNode head) {
        if(head == null)
            return null;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode newPre = newHead;

        RandomListNode tmp = head.next;
        while(tmp!=null){
            RandomListNode t = new RandomListNode(tmp.label);
            newPre.next = t;
            newPre = t;
            tmp = tmp.next;
        }
        tmp = newHead;
        while(tmp!=null){
            tmp = tmp.next;
        }
        tmp = head;
        RandomListNode newTmp = newHead;
        while(tmp!=null){
            if(tmp.random!=null){
                int label = tmp.random.label;
                RandomListNode cur = newHead;
                while(label!=cur.label)
                    cur = cur.next;
                newTmp.random = cur;
            }
            else
                newTmp.random = null;
            tmp = tmp.next;
            newTmp = newTmp.next;
        }
        return newHead;
    }
    public static void main(String[] args){
        RandomListNode head = new RandomListNode(1);
        head.next = new RandomListNode(2);
        head.random = head.next;

        head.next.next = new RandomListNode(3);
        head.next.random = head.next.next;

        head.next.next.next = new RandomListNode(4);
        head.next.next.random = head.next.next.next;

        head.random = null;
        head.next.random = head.next.next.next;


        RandomListNode newH = copyRandomList(head);
        while(newH!=null){
            System.out.println(newH.label+" "+newH.next+" "+newH.random);
            newH = newH.next;
        }
    }
}
